package J.算法.动态规划;

/**
 * 背包问题学习
 */
public class _A_PackagePro {
    public static void main(String[] args) {
        int[] w ={1,2,3,4};
        int[] val = {1500,3000,2000};
        int m=4;//背包最大容量
        int n =w.length;//物品个数
        int[][] v = new int[n+1][m+1];//v[i][j]表示满足容量为j时放入第i个物品形成的最大价值

        //存放背包结果的
        int[][] res = new int[n+1][m+1];


        //初始化数组 第一行 第一列全0
        for (int i= 0;i<m;i++){
            v[i][0]=0;
        }
        for (int i= 0;i<n;i++){
            v[0][i]=0;
        }


        for (int i =1;i<v.length;i++){
            for (int j = 1; j < v[0].length; j++) {
                //i从1开始 但在v数组中要从0开始
                if (w[i] > j){
                    v[i][j] = v[i-1][j];
                }else {
                    //原公示： val【i-1】 w[j-1]

                    //  v[i][j] = Math.max(v[i-1][j],val[i-1]+v[i-1][j-w[i-1]]);
                //为存放结果使用if else==没怎么明白
                    if(v[i-1][j]<val[i-1]+v[i-1][j-w[i-1]]){
                        v[i][j]=val[i-1]+v[i-1][j-w[i-1]];
                        res[i][j] = 1;
                    }else {
                        v[i][j]=v[i-1][j];
                    }
                }
            }
        }
    }
}
